package main

import "fmt"


func main() {
	arr := []int{1, 3, 5, 6}
	res := searchInsert(arr, 0)
	fmt.Println(res)
}

// 找到不大于这个这个数的索引，假设无重复元素
func searchInsert(nums []int, target int) int {
	l, r, minindex := 0, len(nums)-1, 0

	for l <= r { // 有的时候需要=有的时候不需要，很尴尬
		mid := l + ((r - l) >> 1)
		if nums[mid] == target {
			return mid
		} else if target > nums[mid] { // 比mid大所以应该插入到 mid+1 后面
			l = mid + 1
			minindex = l
			if l >= len(nums) || target < nums[l] { //这个跳出很关键
				break
			}
		} else { // 小于的话，应该插入到mid之前
			r = mid - 1
			minindex = r
		}
	}
	if minindex < 0 { //为了防止-1的情况
		minindex = 0
	}

	return minindex
}
